// 多线程快速排序
// ./exam_sort_test [n] [cutoff]
#include "thread.h"
#include "mem.h"

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

static int cutoff = 10000;

struct args {
    int *a;
    int lb, ub;
};

static int
partition(int *a, int i, int j)
{
    int k = i;
    int v = a[k];
    int t;

    j++;
    while (i < j) {
        i++; while (i < j && a[i] < v) i++;
        j--; while (         a[j] > v) j--;
        if (i < j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        Thread_pause(); // Simulate preempting
    }
    t = a[k]; 
    a[k] = a[j];
    a[j] = t;
    return j;
}

static int
quick(void *cl)
{
    struct args *ar = cl;
    int lb = ar->lb, ub = ar->ub;
    if (lb < ub) {
        int k = partition(ar->a, lb, ub);
        ar->lb = lb;
        ar->ub = k-1;
        if (k - lb > cutoff) {
            Thread_T t = Thread_new(quick, ar, (int)sizeof(*ar));
            printf("thread:%p sorted %d..%d\n", t, lb, k-1);
        } else {
            quick(ar);
        }

        ar->lb = k+1;
        ar->ub = ub;
        if (ub - k > cutoff) {
            Thread_T t = Thread_new(quick, ar, (int)sizeof(*ar));
            printf("thread:%p sorted %d..%d\n", t, k+1, ub);
        } else {
            quick(ar);
        }
    }
    return 0;
}

static void
sort(int *x, int n)
{
    struct args ar;
    ar.a = x;
    ar.lb = 0;
    ar.ub = n-1;
    Thread_new(quick, &ar, (int)sizeof(ar));
    Thread_join(NULL);
}

int main(int argc, char **argv)
{
    int n = 100*1000;
    if (argc >= 2)
        n = atoi(argv[1]);
    if (argc >= 3)
        cutoff = atoi(argv[2]);

    assert(n > 0);

    Thread_init(0);

    int *x = ALLOC(n*sizeof(*x));
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        x[i] = rand();

    sort(x, n);

    int i;
    for (i = 1; i < n; i++) {
        if (x[i] < x[i-1])
            break;
    }
    assert(i == n);
    Thread_exit(0);
    return 0;
}

